package cn.xaut.优先队列;

import cn.xaut.剑指offer.m20.demo21;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 215. 数组中的第K个最大元素
 */
public class demo215 {

    // 优先队列 1
    public int findKthLargest(int[] nums, int k) {

        // 大顶堆
/*        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });*/
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

        for (int x : nums)
            pq.offer(x);

        for (int i = 0; i < k - 1; i++)
            pq.poll();

        return pq.poll();
    }
    
    // 排序
    public int findKthLargest2(int[] nums, int k) {

        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    // 优先队列 2
    public int findKthLargest3(int[] nums, int k) {

        // 小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < k; i++) 
            pq.offer(nums[i]);

        for (int i = k; i < nums.length; i++) {
            if (nums[i] > pq.peek()) {
                pq.poll();
                pq.offer(nums[i]);
            }
        }
        
        return pq.peek();
    }

    public static void main(String[] args) {

        System.out.println(new demo215().findKthLargest3(new int[]{3, 2, 1, 5, 6, 4}, 2));//5
        System.out.println(new demo215().findKthLargest3(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));//4
    }
}
